
#include <stdio.h>
#include <stdlib.h>

#include <time.h>


void loadMatrix(char* filename);
int readNumberOfNodes(FILE* matrixFile);

int countEdges();
void countDegree();
void sortVertexesByDegree();


void printMatrix();
void printMatrix2(int** arr, int x, int y);
void printArray(int* arr, int n);
void printNeighbours();

void initializeSolutionArrays();

void initializeStack();
int* pop();
int push(int i, int depth);

void pushFirstNodes();

void cleanup();
void solve();

int isSolution();
int isInSolution(int i, int j);

/*matice sousednosti*/
int** matrix;

/*pocet uzlu*/
int n;

/*pocet hran*/
int e;

/*pole stupnu uzlu*/
int* degree;

/*trivialni horni mez*/
int upperBound;

/*trivialni dolni mez*/
int lowerBound;

/*pole uzlu serazenych sestupne (od nejvetsiho) stupne uzlu*/
int* vertexes;

/*pole indexovane cislem uzlu udavajici index v pozici pole vertexes - pro rychly pristup*/
int* vertex_position;

/*zasobnik - pole poli [index uzlu, hloubka uzlu]*/
int** stack;
int stack_size;
int stack_pointer;

/*pole zvolenych uzlu*/
int* solution;
int solution_size;

/*nejlepsi nalezene reseni*/
int* result;



/*casove promenne */
clock_t startTime, endTime;
time_t* time_p;
double elapsed;

time_t t1;
time_t t2; 



/*********************************

funkce main

*********************************/

int main(int argc, char* argv[]){
  
  if(argc != 2){
    fputs("Pouzijte 1 argument - <jmeno vygenerovaneho souboru s matici sousednosti>\n", stderr);
    exit(1);
  }

  
  loadMatrix(argv[1]);
  
  printf("Nactena matice sousednosti %d x %d:", n, n);  
  printMatrix();
  
  
  e = countEdges();
  printf("Pocet hran v grafu je: %d\n", e);
  
  
  countDegree();
  printf("Stupne uzlu jsou:");
  printArray(degree, n);
  
  //upperBound = n < e ? n/2+n%2 : e/2+e%2;
  upperBound = n-1 < e/2+e%2 ? n-1 : e/2+e%2;
  printf("Trivialni horni mez je: %d\n", upperBound);
  
  sortVertexesByDegree();
  printf("Uzly podle stupne:");
  printArray(vertexes, n);
  printf("Pozice uzlu v poli vertexes:");
  printArray(vertex_position, n);
  printf("Trivialni dolni mez je: %d\n", lowerBound);

  initializeStack();

  initializeSolutionArrays();
  
  //startTime = time(NULL);
  startTime = clock();
  
  t1 = time(NULL);



  pushFirstNodes();

  solve();

  //endTime = time(NULL);
  endTime = clock();
  
  t2 = time(NULL);
  

  elapsed = ((double) (endTime - startTime)) / CLOCKS_PER_SEC;

  #ifdef DEBUG
	  printf("Nactena matice sousednosti %d x %d:", n, n);  
	  printMatrix();  
	  printf("Pocet hran v grafu je: %d\n", e);
	  printf("Stupne uzlu jsou:");
	  printArray(degree, n);
	  printf("Uzly podle stupne:");
	  printArray(vertexes, n);
	  printf("Trivialni dolni mez je: %d\n", lowerBound);
  #endif

  printf("Cas vypoctu: %e\n", elapsed);
  
  printf("Cas startu: %s\n", ctime(&t1));
  printf("Cas konce: %s\n", ctime(&t2));

  cleanup();

  return 0;
}



/*********************************

funkce vlozi na zasobnik vsechny uzly (prvni krok expanze)

*********************************/
void pushFirstNodes(){
   int i;

   for(i=n-1; i>=0; i--){
		push(vertexes[i], 1);
   }
}



/*********************************

funkce hledajici reseni uzloveho pokryti

*********************************/
void solve(){

  int i, depth, position, temp;
  int* arr;

  while(1){
	
      //vyber uzel ze zasobniku
      arr = pop();
  	
  	if(arr == NULL){
  		/*konec vypoctu*/
		printf("\nNejlepsi nalezene reseni je velikosti %d:\n", upperBound);
		printArray(result, upperBound);
		break;
  	}else{
  		depth = arr[1];
  		solution[depth-1] = arr[0];
		solution_size = depth;

		#ifdef DEBUG
			printf("Zkousim kombinaci: ");		
			printArray(solution, solution_size);
		#endif
  	}
  
    if((depth >= lowerBound) && (depth <= upperBound) && (isSolution() == 1)){

  
  		if(depth==lowerBound){
  		    	printf("Reseni: ");
		       printArray(solution, solution_size);
  			printf("Nalezeno optimalni reseni, koncim\n");
  			return;
  		}else{
  			//jine reseni    			
  			if(depth<=upperBound){
  				//lepsi nez dosud nejlepsi - aktualizuj horni mez
  				upperBound = depth;
  				
  				#ifdef DEBUG
			          printf("Reseni: ");
		       	   printArray(solution, solution_size);
  				   printf("Reseni je aktualne nejlepsi a ma pocet uzlu %d\n", depth);
			       #endif  				

				//uloz reseni
				for(i=0; i<depth; i++){
					temp = solution[i];
					result[i] = temp;
				}
  			}else{
  			    #ifdef DEBUG
  			       printf("Reseni: ");
		              printArray(solution, solution_size);
  			       printf("Reseni je horsi, nez predchozi nalezene\n");
  			    #endif
  			}
  		}

  	}else if(depth+1>upperBound){
  		//maximalni hloubka dosazena - neexpanduj dal
  		continue;
	}else{
  
  		//expand	
		position = vertex_position[arr[0]];
  		for(i = n-1; i > position; i--){
  			push(vertexes[i], depth + 1);
  		}
  
		/*
		printf("Po expanzi\n");
  		printMatrix2(stack, stack_pointer + 1, 2);
		*/
	}
  }
}


/*********************************

funkce overi, zda se jedna o pripustne reseni

*********************************/
int isSolution(){

	int i, j;

	for(i=0; i<n; i++){
		for(j=i; j<n; j++){
			if(matrix[i][j]==1){
				if(isInSolution(i, j) == 0){
					return 0;
				}
			}
		}
	}

	return 1;	
}


/*********************************

funkce overi, zda je hrana (i,j) pokryta

*********************************/
int isInSolution(int i, int j){
	int a;
	for(a=0; a<solution_size; a++){
		if(solution[a]==i || solution[a]==j){
			return 1;
		}
	}
	return 0;
}



/*********************************

funkce uvolni zaalokovanou pamet

*********************************/
void cleanup(){
  int i;

  for(i=0; i<n; i++){
	  free(matrix[i]);
  }

  free(matrix);

  free(vertexes);
  free(vertex_position);
  free(degree);

  for(i=0; i<stack_size; i++){
	  free(stack[i]);
  }
  free(stack);

  free(solution);
  free(result);
}

/*********************************

funkce spocte sousedy ke kazdemu uzlu a seradi je do pole vertexes

*********************************/
void sortVertexesByDegree(){
  int i, j, x = 0, sum = 0, min = 1000, max = -1000;

  for(i=0; i<n; i++){
	  if(degree[i]>max){
		  max = degree[i];
		  if(degree[i]<min){
			min = degree[i];
		  }
	  }else if(degree[i]<min){
		  min = degree[i];
	  }
  }

  if(( vertexes = (int*) malloc(n * sizeof(int))) == NULL){
	  fputs("Chyba alokace pole vertexes\n", stderr);
	  exit(-1);
  }

  if(( vertex_position = (int*) malloc(n * sizeof(int))) == NULL){
	  fputs("Chyba alokace pole vertex_position\n", stderr);
	  exit(-1);
  }
  
  for(i=max; i>=min; i--){
	
  	for(j=0; j<n; j++){
  	  if(i==degree[j]){
  	    vertex_position[j] = x;
    		vertexes[x++] = j;
    		if(sum < e){
    			sum += i;
    			lowerBound++;			
    		}
  	  }
  	}
  }
  
}


/*********************************

funkce spocte stupne uzlu

*********************************/
void countDegree(){
  
  int i, j;
  
  if(( degree = (int*) malloc(n * sizeof(int))) == NULL){
	  fputs("Chyba alokace pole degree\n", stderr);
	  exit(-1);
  }
  
  for(i=0; i<n; i++){
    degree[i] = 0;
    for(j=0; j<n; j++){
      degree[i] += matrix[i][j];
    }
  }
   
}


/*********************************

funkce spocte pocet hran grafu

*********************************/
int countEdges(){
  int i, j, sum;
  
  sum = 0;
  
  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      sum += matrix[i][j];
    }
  }

  return sum / 2;
}




/*********************************

funkce nacte matici ze zadaneho souboru

*********************************/

void loadMatrix(char* filename){

  FILE* matrixFile;
  char number;
  
  int i, j;
  
  matrixFile = fopen(filename, "r");
  
  if(!matrixFile){
    fputs("Nepodarilo se otevrit vstupni soubor.\n", stderr);
    exit(-1);
  }

  n = readNumberOfNodes(matrixFile);  
  
  if(( matrix = (int**) malloc(n * sizeof(int*))) == NULL){
	  fputs("Chyba alokace matrix\n", stderr);
	  exit(-1);
   }

 
  for(i=0; i<n; i++){

     if(( matrix[i] = (int*) malloc(n * sizeof(int))) == NULL){
  	  fputs("Chyba alokace\n", stderr);
  	  exit(-1);
     }

    for(j=0; j<n; j++){
         
      number = fgetc(matrixFile);             

      if((number == EOF) || (number == '\n')){
          if((number == EOF) && ((i<n-1)||(j<n-1))){
            matrix[i][j] = atoi(&number);
  	        printf("konec souboru - soubor neobsahuje dostatek hodnot pro naplneni definovane matice %d x %d\n", n, n);
	          exit(-1);
	        }
          
          if(number == '\n'){
            if(j<n-1){
              printf("radek %d v souboru s matici neobsahuje dostatek hodnot j=%d n-1=%d\n", i+1, j, n-1);
	            exit(-1);
            }
          }

	   }else{            	        
            matrix[i][j] = atoi(&number);
            
            if((number != '0') && (number != '1')){
              fputs("matice sousednosti pouziva jina cisla nez jednicky a nuly!!\n", stderr);
  		        exit(-1);
            }
            
			number = fgetc(matrixFile);
			if(number != ' '){
              fputs("v matici neni za cislem mezera!!\n", stderr);
  		        exit(-1);
            }

	      }
		
     }
     
     number = fgetc(matrixFile);
     if(number != '\n' && number != EOF){
          printf("radek %d matice je prilis dlouhy!!\n", j);
    		  exit(-1);
     }
     
   }
   

  fclose(matrixFile);
}




/*********************************

funkce nacte pocet uzlu grafu

*********************************/
int readNumberOfNodes(FILE* matrixFile){
  
  char* number;
  char* p;
  int countChar;
  int numNodes;
  
     
  if(( number = (char*) malloc(sizeof(char))) == NULL){
	     fputs("Chyba alokace cislo\n", stderr);
	     exit(-1);
  }
  
  countChar = 0;
     
  while(1){
          number = (char*) realloc(number, (countChar+1) * sizeof(char));
	          
          if(number == NULL){
            fputs("Chyba realokace cislo\n", stderr);
            exit(-1);
          }
          
        p = number;
        p += countChar;
        *p = fgetc(matrixFile);
                    

      if((p == number) && ((*p == ' ') || (*p == '\n'))){
	     fputs("ERROR nacitani - soubor obsahuje vice oddelovacu za sebou nebo radek zacina mezerou!\n", stderr);
	     exit(-1);
    	}

      if((*p == ' ') || (*p == EOF) || (*p == '\n')){
          if(*p == EOF){
            *p = 0;
  	        printf("konec souboru - soubor neobsahuje dostatek hodnot pro naplneni definovane matice\n");
	          exit(-1);
	        }          
          
	        *p = 0;
	        	        
          numNodes = atoi(number);
          
          countChar = 0;
          free(number);
          
          break;
      }else{
		      if(((*p <'0') || (*p >'9')) && (*p != '\n')){
	  	      fputs("soubor matice obsahuje pravdepodobne jine znaky nez cisla!!\n", stderr);
		        exit(-1);
		      }
	    }		
      countChar++;
     }
     return numNodes;
}



/*********************************

funkce vytiskne matici sousednosti na vystup

*********************************/
void printMatrix(){
	printMatrix2(matrix, n, n);
}

/*********************************

funkce vytiskne matici o rozmerech x,y na vystup

*********************************/
void printMatrix2(int** arr, int x, int y){
  int i, j;

  printf("\n");
  
  for(i=0; i<x; i++){
   for(j=0; j<y; j++){
    printf("%d ", arr[i][j]);
   }
  printf("\n");
  } 
}

/*********************************

funkce vytiskne pole na vystup

*********************************/
void printArray(int* arr, int x){

  int i;

  for(i=0; i<x; i++){
    printf("%d ", arr[i]);
   }
  printf("\n");
   
}


/*********************************

funkce alokuje zasobnik potrebne velikosti

*********************************/
void initializeStack(){

  int i;
  stack_size = 1;
  stack_pointer = -1;

  stack_size = n * upperBound;

  if(( stack = (int**) malloc(stack_size * sizeof(int*))) == NULL){
	fputs("Chyba alokace zasobniku\n", stderr);
	exit(-1);
  }

  for(i=0; i<stack_size; i++){
    if(( stack[i] = (int*) malloc(2 * sizeof(int))) == NULL){
  		fputs("Chyba alokace zasobniku\n", stderr);
  		exit(-1);
  	}
  }

}


/*********************************

funkce na inicializaci poli reseni

*********************************/  
void initializeSolutionArrays(){
  solution_size = -1;

  if(( solution = (int*) malloc(upperBound * sizeof(int))) == NULL){
	fputs("Chyba alokace solution\n", stderr);
	exit(-1);
  }

  if(( result = (int*) malloc(upperBound * sizeof(int))) == NULL){
	fputs("Chyba alokace result\n", stderr);
	exit(-1);
  }
}

/*********************************

funkce vybere polozku ze zasobniku

*********************************/
int* pop(){
  return stack_pointer==-1?NULL:stack[stack_pointer--];
}

/*********************************

funkce vlozi polozku na zasobnik

*********************************/
int push(int i, int depth){
	if(stack_pointer==stack_size){
		return 0;
	}
	stack_pointer++;
	stack[stack_pointer][0] = i;
	stack[stack_pointer][1] = depth;
	return 1;
}

